Java算法中的栈

Deque（双端队列）在 Java 中，它同时承担了 C++ 中 std::stack 和 std::queue 的角色。

不要使用java中的Stack 类（它是旧 vector 实现的，同步且慢），使用 Deque 接口的实现类 ArrayDeque。

以下是 Deque 的核心 API 整理，按使用场景分类：

1. 初始化

// 必须引入包
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.LinkedList;

// 写法 1：最常用（基于数组，性能好，类似 C++ vector）
Deque<Integer> stack = new ArrayDeque<>();

// 写法 2：基于链表（如果需要频繁在中间插入删除，或者作为链表使用）
Deque<Integer> queue = new LinkedList<>();

2. 当作 栈 (Stack) 使用 (LIFO)

对应 C++ 的 std::stack。

操作都在头部（Head）进行。

注意：Java 的 pop() 会抛异常，所以通常先判断 isEmpty()。或者使用 poll() (返回 null)，但在 Stack 语义下大家习惯用 pop()。

3. 当作 队列 (Queue) 使用 (FIFO)

对应 C++ 的 std::queue。

队尾（Tail）进，队头（Head）出。

4. 当作 双端队列 (Deque) 使用

对应 C++ 的 std::deque。如果你需要两头操作（比如滑窗最大值问题），用这些明确的方法：

记忆技巧：

• offer/poll/peek 是不抛异常的版本（返回 false/null）。
• add/remove/get 是抛异常的版本。
• 刷题时建议用 offer/poll/peek 防止 Crash。

5. 常用通用方法

Deque<Integer> dq = new ArrayDeque<>();

dq.isEmpty();   // 判空，相当于 C++ empty()
dq.size();      // 大小，相当于 C++ size()
dq.contains(x); // 是否包含，O(N) 复杂度
dq.clear();     // 清空

6. 遍历与输出

ArrayDeque 的迭代器是从 Head (栈顶/队头) 到 Tail (栈底/队尾) 的。

假设按顺序 Push 了：1, 2, 3。

栈结构是：[3, 2, 1] (3 是栈顶)。

方式 A：普通的 for-each (从头到尾)

// 栈顶 -> 栈底
for (Integer i : stack) {
    System.out.print(i);
}
// 输出: 321

方式 B：转为 String 输出 (正序需求)

如果你想恢复成存入的顺序 123，有三种办法：

1. 从尾部取 (推荐)：

   while (!stack.isEmpty()) {
       System.out.print(stack.pollLast()); // 移除并打印栈底元素
   }
   

2. 逆序迭代器：

   Iterator<Integer> it = stack.descendingIterator();
   while(it.hasNext()) {
       System.out.print(it.next());
   }
   

3. 转 List 再反转 (慢，不推荐)：

   List<Integer> list = new ArrayList<>(stack);
   Collections.reverse(list);
   

总结速查